package q442_findDuplicates;

import java.util.ArrayList;
import java.util.List;

public class Solution_3 {
    /*
    此处使用的方法
    我们遍历到i时 查看abs(nums[i]) - 1位置的数字
    如果是正数 则取反 否则加入ans
    原理在于 如果1 - n范围内有一个数字出现了两次 意味着我们这样遍历会将两次查看同一个位置的数字
    因此发现负数 也就意味着这个abs(nums[i]) - 1出现了两次
     */
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            int x = Math.abs(nums[i]) - 1;
            if (nums[x] > 0) {
                nums[x] = - nums[x];
            }else {
                ans.add(x);
            }
        }

        return ans;
    }



}
